﻿namespace LeetCodeProject._0001_1000._001_100._91_100._099;

public class Solution
{
    public void RecoverTree(TreeNode root)
    {
        TreeNode prev = null;
        TreeNode n1 = null;
        TreeNode n2 = null;
        foreach (var node in MorrisTraver(root))
        {
            if (prev != null && prev.val > node.val)
            {
                if (n1 == null) n1 = prev;
                n2 = node;
            }

            prev = node;
        }

        if (n1 != null)
        {
            var tmp = n1.val;
            n1.val = n2.val;
            n2.val = tmp;
        }
    }

    private IEnumerable<TreeNode> MorrisTraver(TreeNode node)
    {
        while (node != null)
        {
            if (node.left == null)
            {
                yield return node;
                node = node.right;
            }
            else
            {
                var prev = node.left;
                while (prev.right != null && prev.right != node)
                    prev = prev.right;
                if (prev.right == null)
                {
                    prev.right = node;
                    node = node.left;
                }
                else
                {
                    prev.right = null;
                    yield return node;
                    node = node.right;
                }
            }
        }
    }
}